Houdiniメモ : 多角形の内外判定

Winding Number Algorithm

Winding Number Algorithmを利用した多角形の内外判定

code:Winding_Number_Algorithm(c)

int numpt = npoints(1);

float totalRadian = 0.0;

for (int i = 0; i < numpt; i++) {

vector p1 = point(@OpInput2, "P", i); // 多角形のi番目の頂点を取得

vector p2 = point(@OpInput2, "P", (i + 1) % numpt); // 多角形の(i+1)番目の頂点を取得

vector dir1 = normalize(p1 - @P); // ポイントと多角形頂点を結ぶ線その1

vector dir2 = normalize(p2 - @P); // ポイントと多角形頂点を結ぶ線その2

float radian = acos(dot(dir1, dir2)); // 二つの線がなす角

totalRadian += (radian); // なす角を加算していく

}

if (degrees(totalRadian) < 359) { // 角度の合計が360°未満なら多角形の外側

@Cd = {1, 0, 0}; // 赤くする

}

■使用例

多角形の外側のポイントが赤くなります。

https://gyazo.com/186d88c8aec39ab97a30672b34adafb6

■欠点

Winding Number Algorithmでは、多角形に180°を超えるような内角が含まれているとうまく内外判定できません。

https://gyazo.com/9f6b09095299e113027c06c33b8ef9c0

Crossing Number Algorithm

Crossing Number Algorithmを利用した多角形と点の内外判定

code:Crossing_Number_Algorithm(c)

////////////////////////////////////////////////////////

// Crossing Number Algorithmを利用した多角形と点の内外判定//

////////////////////////////////////////////////////////

int n = npoints(@OpInput2); // 第2インプットのポイント数

int pt1 = 0; // ポイントインデックス(1番目)

int pt2 = 1; // ポイントインデックス(2番目)

int crossCount = 0; // ポイントからX方向へ線を伸ばしたときに多角形と交差した回数

float x = @P.x;

float z = @P.z;

for (int i = 0; i < n; i++) {

vector p1 = point(@OpInput2, "P", pt1);

vector p2 = point(@OpInput2, "P", pt2);

if ((p1.z - z) * (p2.z - z) < 0) { // zはp1.zとp2.zの間にある

// 直線の方程式で交点のX座標を求める

float crossX = p1.x + (p2.x - p1.x) / (p2.z - p1.z) * (z - p1.z);

if (x < crossX) { // 交点がポイントの右側

crossCount++;

}

}

pt1 = pt2;

pt2 = (pt2 == n - 1) ? 0 : (pt2 + 1);

}

if (crossCount % 2 == 0) { // 偶数回なら多角形の外側

@Cd = {1, 0, 0}; // 多角形の外側のポイントは赤くする

}

■結果

Crossing Number Algorithmでは180°を超えるような内角が含まれた多角形(凹型多角形)でも判定できます。

https://gyazo.com/f46ee354055c536050b5727925c97f5b